package labuladong.动态规划;

import java.util.Arrays;

public class 最长递增子序列 {

    public static void main(String[] args) {
        System.out.println(lengthOfLITS(new int[]{1, 4, 3, 4, 2, 3}));
        System.out.println(lengthOfLITS2(new int[]{1, 4, 3, 4, 2, 3}));
    }

    public static int lengthOfLITS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int maxLen = 0;
        for (int i=1; i<nums.length; i++) {
            for (int j=0; j<i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }

    public static int lengthOfLITS2(int[] nums) {
        if (nums.length == 0) return 0;
        int[] top = new int[nums.length];
        int piles = 0;
        for (int i=0; i<nums.length; i++) {
            int poker = nums[i];
            int left = 0; int right = piles;
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid+1;
                } else {
                    right = mid;
                }
            }
            if (piles == left) piles++;
            top[left] = poker;
        }
        return piles;
    }
}
